package com.ruijixiang.leetcode.hot100;

import java.util.HashSet;
import java.util.Set;

public class leetcode0142 {
    /**
     * 方法一：快慢指针
     * 方法二：哈希表
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head){
        // 方法一：快慢指针
//        ListNode fast=head;
//        ListNode slow=head;
//        while(true){
//            if(fast==null || fast.next==null){
//                return null;
//            }else{
//                fast=fast.next.next;
//            }
//            slow=slow.next;
//            if(fast==slow) break;
//        }
//        fast=head;
//        while(fast!=slow){
//            fast= fast.next;
//            slow=slow.next;
//        }
//        return fast;

        // 方法二：哈希表
        ListNode pos=head;
        Set<ListNode> set=new HashSet<>();
        while(pos!=null){
            if(set.contains(pos)) return pos;
            set.add(pos);
            pos=pos.next;
        }
        return pos;
    }
}
